void bfs()
{
	memset(idx,0,sizeof(idx));
	queue<int>q;
	q.push(S);
	idx[S]=1;
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=head[u];~i;i=e[i].next)
		{
			int v=e[i].v;
			if(!e[i].val||idx[v])continue;
			idx[v]=idx[u]+1;
			q.push(v);
		}
	}
	return;
}
int dfs(int u,int _min)
{
	if(u==T)return _min;
	int ret=0,k;
	for(int i=cur[u];~i;i=e[i].next)
	{
		int v=e[i].v;
		cur[u]=i;
		if(!e[i].val||idx[v]!=idx[u]+1)continue;
		k=dfs(v,min(_min-ret,e[i].val));
		e[i].val-=k;
		e[i^1].val+=k;
		ret+=k;
		if(ret==_min)break;
	}
	return ret;
}
int dinic()
{
	int ret=0;
	while(true)
	{
		bfs();
		if(!idx[T])break;
		memcpy(cur,head,sizeof(head));
		ret+=dfs(S,INF);
	}
	return ret;
}
